1. Field of the Invention
The present invention relates generally to the computation of contact forces and, more particularly, to the computation of optimal contact forces with friction.
2. Description of the Prior Art
The present invention is concerned with mechanisms having closed kinematic chains involving multiple frictional contacts between an actively controlled structure and an object. In such situations, an important problem is choosing an optimal distribution of contact forces to achieve some objective. One example is grasping by a robotic hand, where the kinematic chains are closed through the object grasped. Another example is cooperating manipulators, where the kinematic chains are closed through the load. A third example is multi-legged vehicles, where the kinematic-chains are closed through the terrain.
The issues may be illustrated by considering grasping by a robotic hand, where the problem is choosing a set of contact forces used to grasp an object. A survey of robotic grasping may be found in Bicchi and Kumar, “Robotic grasping and contact: A review”, IEEE International Conference on Robotics and Automation (ICRA), pp 348-353, 2000.
The most basic requirement is the ability to restrain an object against a specified external wrench, for example that due to gravity. An early paper discussing this issue is Kerr and Roth, “Analysis of multifingered hands”, The International Journal of Robotic Research, 4(4): 3-17, 1986. There may be many possible choices that achieve equilibrium. A good choice is one with minimum force, as measured by some function of the contact forces. Various formulations of the problem use various specific functions, as described below. The problem of finding a set of optimal forces is referred to as the “force optimization problem” or “FOP”.
A related problem is the ability to resist an arbitrary external wrench. This is called “force closure”. This is discussed in Kirkpatrick et al. “Quantitative Steinitz's theorems with applications to multifingered grasping”, Proceedings of the 20th ACM Symposium on Theory of Computing, pages 341-351, 1990 and in Ferrari and Canny, “Planning optimal grasps, Proceedings of the 1992 IEEE International Conference on Robotics and Automation, pages 2290-2295, Nice, France, May 1992.
There are several other related problems. One is finding the minimum over a set of related force optimization problems. For example, this arises when choosing a desirable grasp configuration on an object. A FOP is solved for each grasp configuration and the overall computation finds the configuration with the minimum grasping force.
Another related problem is finding the maximum over a set of related force optimization problems. For example, this arises when finding the maximum grasping force that is required to move an object along a given trajectory. Each point on the trajectory has an associated external wrench and the computation finds the maximum grasping force over the set of external wrenches.
The basic force optimization problem has been studied for several years. Kerr and Roth, supra., was an early work in this area. Another early paper is Cheng and Orin, “Efficient Algorithms for Optimal Force Distribution, the Compact Dual LP Method”, IEEE Trans. on Robotics and Automation, 6(2): pp. 178-187, April 1990. In both of these papers, the FOP is formulated (approximately) as a linear programming problem (LP), by approximating the friction force limit constraints as linear inequalities.
The force optimization problem was formulated as a quadratic programming problem in a paper by Nahon and Angeles, “Real-Time Force Optimization in Parallel Kinematic Chains under Inequality Constraints”, IEEE Trans. on Robotics and Automation, 8(4), pp 439-450, August 1992. In that paper, the friction force limit are approximated by linear inequalities, but the objective function is that of minimizing the internal force, a quadratic function of the contact forces. An application of quadratic programming to a legged vehicle is described in Chen, et al, “Optimal Force Distribution for the Legs of a Quadruped Robot, Machine Intelligence & Robotic Control, Vo. 1., No. 2, pp 87-94, 1999.
In the late 1990s, several exact formulations of the FOP were obtained by expressing it as a convex optimization problem. One such paper is Buss et al, “Dexterous hand grasping force optimization, “IEEE Trans. Robotics and Automation, 12:406-418, June 1996; see also Buss, et al, “Dikin-type algorithms for dexterous grasping force optimization”, International Journal of Robotics Research, 17(8): pp. 831-839, 1998, and U. Helmke, et al. “Quadratically convergent algorithms for optimal dexterous hand grasping”, IEEE Trans. on Robotics and Automation, 18:138-146, April 2002.
Particular formulations of convex optimization problem involve matrix inequalities or second-order cone inequalities. The paper by Han et al, “Grasp analysis as linear matrix inequality problems”, IEEE Trans. on Robotics and Automation, 16:663-674, December 2000, expresses the FOP using (linear) matrix inequalities, so the resulting optimization problem is a “semidefinite programming problem” or “SDP”. The FOP is formulated as a “second-order cone problem” or “SOCP” in Lobo et al, “Applications of second-order cone programming”, Linear Algebra and its Applications, 284:193-228, November 1998.
These formulations reduce the problem to a standard convex optimization problem. Hence, the problems can be solved by a variety of methods for nonlinear convex optimization developed in the 1990s. The text by Boyd and Vandenberghe, Convex Optimization, Cambridge University Press, 2004, describes several such methods. General-purpose software packages for solving an LP, SOCP, and SDP are now widely available. The paper Mittelmann, “An independent benchmarking of SDP and SOCP solvers”, Mathematical Programming, Series B, 95:407-430, 2003 gives comparative benchmarking of some of these software packages.
Limitations of the Prior Art
There is still, however, a need for faster methods for solving the force optimization problem. Certain real-time applications present such a requirement. The need to solve a large number of force optimization problems presents another requirement. For example, consider the problem of optimizing the position and orientation of a manipulator, relative to an object, using the minimum force required to grasp the object as the objective. This is the (nonconvex) problem of optimizing the contact points at which to grasp a given object. This can be done using an outer search loop that generates candidate manipulator positions and orientations; for each candidate, it is necessary to find the resulting contact points, and then solve the associated FOP to determine the minimum force required to grasp the object. Such an algorithm can require the solution of hundreds of force optimization problems. Other examples are described below.
Hence, there is a need for a system and method able to solve the force optimization problem and related problems very rapidly.